package lc.优先队列;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/28
 */
public class 剑指Offer41_数据流中的中位数 {

    Queue<Integer> A, B;
    public 剑指Offer41_数据流中的中位数() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半

    }

    public void addNum(int num) {

        // 说明a的元素更多
        if (A.size() != B.size()) {
            // 保证b添加的数是a里最小的
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }

    }

    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}
